public class Main {

    /**
     * 两两交换链表中的节点
     * https://leetcode.cn/problems/swap-nodes-in-pairs/
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下
     * 完成本题（即，只能进行节点交换）。
     */
    public static void main(String[] args) {
        System.out.println("hello world >_O");
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        ListNode answer = new Main().swapPairs(head);
        while (answer != null) {
            System.out.println(answer.val);
            answer = answer.next;
        }
    }

    public ListNode swapPairs(ListNode head) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode previous = dummyHead;
        ListNode temporary;
        ListNode temporaryNext;
        while (previous.next != null && previous.next.next != null) {
            temporaryNext = previous.next.next.next;
            temporary = previous.next;
            previous.next = previous.next.next;
            previous.next.next = temporary;
            previous.next.next.next = temporaryNext;
            previous = previous.next.next;
        }
        return dummyHead.next;
    }

    public ListNode swapPairs2(ListNode head) {
        // 退出条件：头结点为空或者头结点后一个结点为空
        if (head == null || head.next == null) {
            return head;
        }
        ListNode next = head.next;
        // 递归
        ListNode newNode = swapPairs2(next.next);
        // 结点两两交换
        next.next = head;
        head.next = newNode;

        return next;
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) {
        this.val = val;
    }
}